#include <stdio.h>
#include <stdlib.h>

#include "mtd_sim.h"
#include "yaffs_guts.h"
#include "yaffs_yaffs2.h"

#include "yaffs_read.h"

#include "file_list_tree.h"


struct yaffs_block_index {
	int seq;
	int block;
};

const static char *yaffs_block_state_str[] = {"unknown", "scanning", "needs_scan",
					"empty", "allocating", "full", 
					"dirty", "checkpoint", "collecting", 
					"dead"};

static int 
yaffs2_ybicmp(const void *a, const void *b)
{
	int aseq = ((struct yaffs_block_index *)a)->seq;
	int bseq = ((struct yaffs_block_index *)b)->seq;
	int ablock = ((struct yaffs_block_index *)a)->block;
	int bblock = ((struct yaffs_block_index *)b)->block;

	if (aseq == bseq)
		return ablock - bblock;

	return aseq - bseq;
}

static int
file_list_tree_cmp(struct file_trunk_list *a, struct file_trunk_list *b)
{
	return (int)a->obj_id - (int)b->obj_id;
}


RB_PROTOTYPE(file_list_tree_t, file_trunk_list, rb_entry, file_list_tree_cmp);
RB_GENERATE(file_list_tree_t, file_trunk_list, rb_entry, file_list_tree_cmp);

struct file_list_tree_t file_list_tree;

static int
query_init_block_state(struct mtd_info *mtd, int block_no,
		enum yaffs_block_state *state, u32 *seq_number)
{
	int retval;

	//yaffs_trace(YAFFS_TRACE_MTD, "nandmtd2_query_block %d", block_no);
	retval =
	    mtd->block_isbad(mtd,
			     block_no * chunksPerBlock *
			     totalBytesPerChunk);

	if (retval) {
	//	yaffs_trace(YAFFS_TRACE_MTD, "block is bad");

		*state = YAFFS_BLOCK_STATE_DEAD;
		*seq_number = 0;
	} else {
		struct yaffs_ext_tags t;

		yaffs_read_chunk_with_tags(mtd, block_no *
					 chunksPerBlock, NULL, &t);

		if (t.chunk_used) {
			*seq_number = t.seq_number;
			*state = YAFFS_BLOCK_STATE_NEEDS_SCAN;
		} else {
			*seq_number = 0;
			*state = YAFFS_BLOCK_STATE_EMPTY;
		}
	}
	//yaffs_trace(YAFFS_TRACE_MTD,
	//	"block is bad seq %d state %d", *seq_number, *state);

	if (retval == 0)
		return YAFFS_OK;

	return YAFFS_FAIL;
}

static void
debug_print_file_info(struct mtd_info *mtd, struct file_list_tree_t *tree)
{
	struct list_head *ptr_list;
	struct file_trunk *ptr_list_ele;
	struct file_trunk_list *ptr_tree_ele;
	struct yaffs_ext_tags tags;

	void *data;
	struct yaffs_obj_hdr *phdr;

	data = malloc(totalBytesPerChunk);
	phdr = (struct yaffs_obj_hdr *)data;

	RB_FOREACH(ptr_tree_ele, file_list_tree_t, tree) {

		printf("obj_id = %d (parent %d):\n", ptr_tree_ele->obj_id,
				ptr_tree_ele->parent_object ? ptr_tree_ele->parent_object->obj_id : -1);
		list_for_each(ptr_list, &ptr_tree_ele->chunk_list) {

			ptr_list_ele = list_entry(ptr_list, struct file_trunk, list_entry);
			yaffs_read_chunk_with_tags(mtd, ptr_list_ele->trunk_number, NULL, &tags);

			if (tags.chunk_id == 0){
				yaffs_read_chunk_with_tags(mtd, ptr_list_ele->trunk_number, data, &tags);
				printf("\tchunk %d (size: %d, global chunk num: %d, %s)\n",
						tags.chunk_id,
						phdr->file_size,
						ptr_list_ele->trunk_number, 
						phdr->is_shrink ? "[s]" : "[]" );
			} else
				printf("\tchunk %d (%d bytes, global chunk num: %d)\n", 
						tags.chunk_id, 
						tags.chunk_id == 0 ? -1 : tags.n_bytes,
						ptr_list_ele->trunk_number);
			
			
		} /* list_for_each */
	} /* RB_FOREACH */

	free(data);
}

static int
construct_directory_tree(struct mtd_info *mtd, struct file_list_tree_t *tree)
{
	int r, parent_obj_id, found_header;
	struct file_trunk_list tmp_tree_ele, *ptr_tree_ele;
	struct file_trunk *ptr_list_ele;
	struct list_head *ptr_list_head;
	struct yaffs_ext_tags tags;

	void *data = NULL;

	data = malloc(totalBytesPerChunk);

	RB_FOREACH(ptr_tree_ele, file_list_tree_t, tree) {
		if (list_empty(&ptr_tree_ele->chunk_list)) {

			//printf("Empty file chunk list! (obj %d)\n", ptr_tree_ele->obj_id);
			goto error;
		}

		found_header = 0;
		list_for_each(ptr_list_head, &ptr_tree_ele->chunk_list) {

			ptr_list_ele = list_entry(ptr_list_head, struct file_trunk, list_entry);
			if (ptr_list_ele->tags.chunk_id == 0) {
				found_header = 1;
				break;
			}
		}

		if (!found_header) {

			//printf("no header is found for an object! (obj %d) \n", ptr_tree_ele->obj_id);
			ptr_tree_ele->parent_object = NULL;
			ptr_tree_ele->obj_type = YAFFS_OBJECT_TYPE_UNKNOWN;
			continue;
			//goto error;
		}

		if ((r = yaffs_read_chunk_with_tags(mtd, ptr_list_ele->trunk_number, data, &tags)) != YAFFS_OK) {

			//printf("Cannot read chunk %d !(obj %d)\n", ptr_list_ele->trunk_number, ptr_tree_ele->obj_id);
			goto error;
		}

		parent_obj_id = ((struct yaffs_obj_hdr *)data)->parent_obj_id;
		ptr_tree_ele->obj_type = ((struct yaffs_obj_hdr *)data)->type;
		
		if (parent_obj_id == YAFFS_OBJECTID_ROOT)
			ptr_tree_ele->parent_object = NULL;

		else if (parent_obj_id > YAFFS_OBJECTID_DELETED) {

			tmp_tree_ele.obj_id = parent_obj_id;
			ptr_tree_ele->parent_object = RB_FIND(file_list_tree_t, &file_list_tree, &tmp_tree_ele);
			if (!ptr_tree_ele->parent_object) {
				//printf("obsolete object found! (obj %d, parent %d)\n", ptr_tree_ele->obj_id, parent_obj_id);
			//	goto error;
			}

		} else {

		//	printf("invalid parent object id! (obj %d, parent %d)\n", ptr_tree_ele->obj_id, parent_obj_id);
			continue;
			//goto error;
		}

	} /* RB_FOREACH */

	free(data);
	return 0;
error:
	if (data)
		free(data);

	return -1;
}


/* 
 * adopted from
 * yaffs2_scan_backwards() @ yaffs_yaffs2.c
 *
 */


struct file_list_tree_t *
build_file_list_tree(struct mtd_info *mtd)
{
	int blk, i, r, c, obj_count;
	enum yaffs_block_state state;
	u32 seq_number;
	int n_to_scan = 0;
	struct yaffs_block_index *block_index = NULL;
	struct yaffs_ext_tags tags;

	struct file_trunk* ptmp_trunk_ele;
	struct file_trunk_list tmp_tree_ele, *ptmp_tree_ele;


	block_index = (struct yaffs_block_index *)
		malloc(totalBlocks * sizeof(struct yaffs_block_index));
	
	if (!block_index)
		goto error;

	/* 
	 * NOTE: block 0 is not used by yaffs2
	 */

	for (blk = 0; blk < totalBlocks; blk++){
		query_init_block_state(mtd, blk, &state, &seq_number);
		/*
		 * XXX: Bad blocks and checkpoint data blocks are not
		 * considered here.
		 */
	//	printf("state of block %d is : %s\n", blk, yaffs_block_state_str[state]);
		if (state == YAFFS_BLOCK_STATE_NEEDS_SCAN){
			if (seq_number >= YAFFS_LOWEST_SEQUENCE_NUMBER &&
					seq_number < YAFFS_HIGHEST_SEQUENCE_NUMBER) {
				block_index[n_to_scan].seq = seq_number;
				block_index[n_to_scan].block = blk;
				n_to_scan++;

			} else {
				if (seq_number == YAFFS_SEQUENCE_CHECKPOINT_DATA)
					;//printf("ignored checkpoint block at block %d\n", blk);
				else
					;//printf("invalid block sequence number at block %d (%d)\n", blk, seq_number);
			}
				

		}
	}
	qsort(block_index, n_to_scan, sizeof(struct yaffs_block_index), yaffs2_ybicmp);

	//printf("sorted %d blocks!\n", n_to_scan);

	/* building file logs linked list here: */

	/* we do not use (and skip) summary tags chunks here */
	RB_INIT(&file_list_tree);

	obj_count = 0;

	for (i = n_to_scan - 1; i >= 0; i--) {
		blk = block_index[i].block;
		c = chunksPerBlock - 1;
		
		/* for each chunk in the block (backwards) */
		for (; c >= 0; c--) {
			if ((r = yaffs_read_chunk_with_tags(mtd, blk * chunksPerBlock + c, NULL, &tags)) != YAFFS_OK)
				goto error;

			/* XXX: there are other pseudo objects, see yaffs_guts.h */
			if (1 && tags.obj_id != 0 && tags.obj_id != YAFFS_OBJECTID_SUMMARY){
				ptmp_trunk_ele = (struct file_trunk *)malloc(sizeof(struct file_trunk));
				if (!ptmp_trunk_ele)
					goto error;

				ptmp_trunk_ele->trunk_number = blk * chunksPerBlock + c;
				ptmp_trunk_ele->tags = tags;

				tmp_tree_ele.obj_id = tags.obj_id;

				ptmp_tree_ele = RB_FIND(file_list_tree_t, &file_list_tree, &tmp_tree_ele);
				if (!ptmp_tree_ele) {
					++obj_count;
					ptmp_tree_ele = (struct file_trunk_list *)malloc(sizeof(struct file_trunk_list));
					if (!ptmp_tree_ele)
						goto error;

					ptmp_tree_ele->obj_id = tags.obj_id;
					INIT_LIST_HEAD(&ptmp_tree_ele->chunk_list);
					RB_INSERT(file_list_tree_t, &file_list_tree, ptmp_tree_ele);
				}

	//			list_add_tail(&ptmp_trunk_ele->list_entry, &ptmp_tree_ele->chunk_list);
	//
				/* Branch forward: 
				 * from the very first chunk to the last one */
				list_add(&ptmp_trunk_ele->list_entry, &ptmp_tree_ele->chunk_list);
			} /* if (tags.chunk_use ...) */

		} /* for(; c >= 0; c--) */
		
		
	} /* for (i = n_to_scan - 1; i >= 0; i--) */
	//printf("%d objects collected!\n", obj_count);

	if (construct_directory_tree(mtd, &file_list_tree) < 0)
		goto error;

//	debug_print_file_info(mtd, &file_list_tree);

	return &file_list_tree;
	
error:
	return NULL;

}

void
file_list_tree_iterate(struct mtd_info *mtd, struct file_list_tree_t* tree, int (*func)(struct mtd_info *, struct file_trunk_list *))
{
	struct file_trunk_list *ptr_tree_ele;
	RB_FOREACH(ptr_tree_ele, file_list_tree_t, &file_list_tree)
		func(mtd, ptr_tree_ele);
}
